package leetcode;

/**
 * 在 R 行 C 列的矩阵上，我们从 (r0, c0) 面朝东面开始
 * 
 * 这里，网格的西北角位于第一行第一列，网格的东南角位于最后一行最后一列。
 * 
 * 现在，我们以顺时针按螺旋状行走，访问此网格中的每个位置。
 * 
 * 每当我们移动到网格的边界之外时，我们会继续在网格之外行走（但稍后可能会返回到网格边界）。
 * 
 * 最终，我们到过网格的所有 R * C 个空间。
 * 
 * 按照访问顺序返回表示网格位置的坐标列表。
 * 
 * @author maodou38
 *超出时间限制
 */
public class Solution885_mime {
	int[][] result=null;
	public int[][] spiralMatrixIII(int R, int C, int r0, int c0) {
		 result=new int[R*C][2];
		 result[0]=new int[] {r0,c0};
		 walkAround(1, R, C, r0, c0, R*C-1);
        return result;
	}
	/**
	 * 
	 * @param time
	 * @param R
	 * @param C
	 * @param r c0 当前的起点位置
	 * @param 有多少个格子需要走
	 * @return
	 */
	public void walkAround(int times,int R,int C,int r,int c,int count){
		for (int i=c+1;i<=c+2*times-1;i++) { //向东走  只有纵坐标改变
			if(r<=R-1&&r>=0&&i<=C-1&&i>=0) { //还在矩阵内
				result[R*C-count]=new int[]{r,i};
				count--;
				if(count==0) {
					return;
				}
			}
		}//结束落在（r,c+2*times-1）
		for (int i=r+1;i<=r+2*times-1;i++) {//向南走  只有横坐标改变
			if(c+2*times-1<=C-1&&c+2*times-1>=0&&i<=R-1&&i>=0) {
				result[R*C-count]=new int[]{i,c+2*times-1};
				count--;
				if(count==0) {
					return;
				}
			}
		}//结束落在（r+2*times-1，c+2*times-1）
		for(int i=c+2*times-2;i>=c-1;i--) {//向西走  只有纵坐标改变
			if(r+2*times-1<=R-1&&r+2*times-1>=0&&i<=C-1&&i>=0) {
				result[R*C-count]=new int[]{r+2*times-1,i};
				count--;
				if(count==0) {
					return;
				}
			}
		}//结束落在（r+2*times-1,c-1）
		for(int i=r+2*times-2;i>=r-1;i--) {//向北走  只有横坐标改变
			if(i<=R-1&&i>=0&&c-1>=0&&c-1<=C-1) {
				result[R*C-count]=new int[]{i,c-1};
				count--;
				if(count==0) {
					return;
				}
			}
		}//结束落在（r-1,c-1）
		walkAround(times+1,R,C,r-1,c-1,count);
	}
	
	public static void main(String[] args) {
		int[][] spiralMatrixIII = new Solution885_mime().spiralMatrixIII(5, 6, 1, 4);
		System.out.println(spiralMatrixIII);
	}
}
